class Solution {
public:
    void dfs(vector<int>&A,vector<int>& B,vector<int>& C,int count)
    {
        // 最后一步也就是递归的出口
        if(count == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        // 递归函数的功能即使将A上的盘子借助B移动到C上
        // count就是A上面盘子的数量
        // 第一步将A上面count-1数量的盘子借助C移动到B上
        dfs(A,C,B,count -1);
        // 第二步将A上面的最后一个盘子移动到C上
        C.push_back(A.back());
        A.pop_back();
        // 最后一步是将B上面的所有盘子借助A移动C上
        dfs(B,A,C,count-1);

    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int count = A.size();
        dfs(A,B,C,count);
    }
};